/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package uk.co.dupenois.geometry.combinatorialmap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.TreeSet;
import uk.co.dupenois.geometry.Coordinate;
import uk.co.dupenois.geometry.Edge;

/**
 *
 * @author Max
 */
public class CombinatorialMap {
    private ArrayList<Dart> darts;
    private HashMap<Coordinate, ArrayList<Edge>> vertexToEdges;
    private HashMap<Coordinate, ArrayList<Dart>> vertexToDartEnd;
    private HashMap<Coordinate, ArrayList<Dart>> vertexToDartStart;
    private HashMap<Edge, Dart[]> edgeToDarts;
    private TreeSet<Edge> sortedEdges;
    private TreeSet<Edge> boundaryEdges;
    private ArrayList<Coordinate> boundaryVertices;

    private EdgeComparator edgeComparator;


    private final static String revealIfDartIsOnBoundaryString = "s";
    private final static String revealIfDartIsNotOnBoundaryString = "asasa";
    private final static String boundaryCheckFunctionString = "sasasa";

    protected CombinatorialMap(){
        this.darts = new ArrayList<Dart>();
        this.vertexToDartEnd = new HashMap<Coordinate, ArrayList<Dart>>();
        this.vertexToEdges = new HashMap<Coordinate, ArrayList<Edge>>();
        this.vertexToDartStart = new HashMap<Coordinate, ArrayList<Dart>>();
        this.edgeToDarts = new HashMap<Edge, Dart[]>();
        
        this.edgeComparator = new EdgeComparator();

    }



    public RevealFunctionResult removeEdge(Edge edge) throws CombinatorialMapDegenerateException{
        Dart[] dartsOnEdge = getDartsOnEdge(edge);
        Dart[] dartsWhichMayHaveMeAsSigma;
        ArrayList<Dart> dartsWhichDoHaveMeAsSigma = new ArrayList<Dart>();
        RevealFunctionResult revealedEdges = revealFunction(edge);
        for(Dart me : dartsOnEdge){
            this.vertexToDartEnd.get(me.getEnd()).remove(me);
            this.vertexToDartStart.get(me.getStart()).remove(me);
            this.darts.remove(me);
            //Remove from end and start lists, checking to see if
            //we need to set new sigmas for those darts
            dartsWhichMayHaveMeAsSigma= getDartsWhichStartAt(me.getStart());
            for(Dart dart : dartsWhichMayHaveMeAsSigma){
                if(dart.getSigma().equals(me)){
                    dartsWhichDoHaveMeAsSigma.add(dart);
                }
            }
        }

        this.boundaryEdges.add(revealedEdges.getEdge1());
        this.boundaryEdges.add(revealedEdges.getEdge2());
        this.boundaryVertices.add(revealedEdges.getCommonVertex());

        this.edgeToDarts.remove(edge);
        this.sortedEdges.remove(edge);
        this.boundaryEdges.remove(edge);

//        System.out.println("Removing edge: "+edge.getStart()+"->"+edge.getFinish()+" in edge to darts");

        if(this.vertexToEdges.containsKey(edge.getStart())){
            this.vertexToEdges.get(edge.getStart()).remove(edge);
        }
        if(this.vertexToEdges.containsKey(edge.getFinish())){
            this.vertexToEdges.get(edge.getFinish()).remove(edge);
        }
        //Set Sigma
        for(Dart dart : dartsWhichDoHaveMeAsSigma)setSigma(dart);


        return revealedEdges;

    }
    public Edge getLongestBoundaryEdge(){
        if(this.boundaryEdges.size()<1)return null;
        return this.boundaryEdges.first();
    }
    public Edge[] getBoundaryEdges(){
        return this.boundaryEdges.toArray(new Edge[this.boundaryEdges.size()]);
    }

    public boolean isVertexOnBoundary(Coordinate vertex){
        return this.boundaryVertices.contains(vertex);
    }

    public Coordinate[] getOrderedBoundaryVertices(){
        Edge[] edges = getBoundaryEdges();
        if(edges.length<1) return new Coordinate[0];
        Arrays.sort(edges, Edge.ComparatorCoordinatesMinXMinY);
        //Get furthest left
        Dart currentBoundaryDart = getDartsOnEdge(edges[0])[0];
//        System.out.println("Start Dart "+currentBoundaryDart);
        //Right:
        /* Want the dart going anticlockwise
         * but anticlockwise depends on the dart we start with and what's
         * around it, however if asasas gets me back to the start then
         * we want the opposite to start with
         */
        boolean switchDarts = currentBoundaryDart.function("asasas").equals(currentBoundaryDart);
        //Check there are actually more than 3 edges, otherwise the above is right
        if(switchDarts && edges.length>3){
            currentBoundaryDart = currentBoundaryDart.getAlpha();
        }
        Dart nextBoundaryDart = null;
        Coordinate start = currentBoundaryDart.getStart();
//        System.out.println("Start Dart "+currentBoundaryDart);
        Coordinate next = null;
        ArrayList<Coordinate> coordinates = new ArrayList<Coordinate>();
        coordinates.add(start);
        //Rotate anticlockwise until we hit the start
        ArrayList<Dart> dartList = new ArrayList<Dart>();
        dartList.add(currentBoundaryDart);
        int count = 0;
        while(!start.equals(next)){
            nextBoundaryDart = currentBoundaryDart.getAlpha().getSigma();
            next = nextBoundaryDart.getStart();
            if(!start.equals(next)){
//                System.out.println("Next Dart "+nextBoundaryDart);
                if(coordinates.contains(next)){
                    System.out.println("WARNING: seem to be looping round "+next);
                    System.out.println("nextBoundaryDart: "+nextBoundaryDart);
                    System.out.println("currentBoundaryDart: "+currentBoundaryDart);
                    System.out.println("Coordinates to this point:");
                    for(Coordinate coord: coordinates){
                        System.out.println("\t"+coord);
                    }
                    System.out.println("Darts to this point:");
                    for(Dart d: dartList){
                        System.out.println("\t"+d);
                    }
                    throw new IllegalArgumentException("something is wrong");
                }
                currentBoundaryDart = nextBoundaryDart;
                dartList.add(currentBoundaryDart);
                coordinates.add(next);
            }
            if(count==1000){
                //Let memory catch up
                try {Thread.sleep(50);} catch (InterruptedException ex) {}
                count = 0;
            }
            count++;
        }
        return coordinates.toArray(new Coordinate[coordinates.size()]);
    }

    public Coordinate[] getVertices(){
        return this.vertexToDartEnd.keySet().toArray(new Coordinate[this.vertexToDartEnd.size()]);
    }

    public Dart[] getDarts(){
        return this.darts.toArray(new Dart[this.darts.size()]);
    }

    public Edge[] getEdges(){
        return this.sortedEdges.toArray(new Edge[this.sortedEdges.size()]);
    }

    public Dart[] getDartsOnEdge(Edge edge){
        Dart[] dartsOnEdge = this.edgeToDarts.get(edge);
        if(dartsOnEdge!=null){
            return dartsOnEdge;
        }
//        System.out.println("Could Not Find edge: "+edge.getStart()+"->"+edge.getFinish()+" in edge to darts");
        return new Dart[0];
    }

    public Dart[] getDartsWhichEndAt(Coordinate vertex){
        ArrayList<Dart> dartsWhichEnd = this.vertexToDartEnd.get(vertex);
        if(dartsWhichEnd!=null){
            return dartsWhichEnd.toArray(new Dart[dartsWhichEnd.size()]);
        }
        return new Dart[0];
    }
    public Dart[] getDartsWhichStartAt(Coordinate vertex){
        ArrayList<Dart> dartsWhichStart = this.vertexToDartStart.get(vertex);
        if(dartsWhichStart!=null){
            return dartsWhichStart.toArray(new Dart[dartsWhichStart.size()]);
        }
        return new Dart[0];
    }



    public static CombinatorialMap createCombinatorialMap(Edge[] edges) throws CombinatorialMapException{
        CombinatorialMap newMap = new CombinatorialMap();
        newMap.generate(edges);
        return newMap;
    }
    protected void generate(Edge[] edges) throws CombinatorialMapException{
        Dart dart1;
        Dart dart2;
        for(Edge edge : edges){
            dart1 = new Dart(edge.getStart(), edge.getFinish(), edge);
            dart2 = new Dart(edge.getFinish(), edge.getStart(), edge);
            dart1.setAlpha(dart2);
            dart2.setAlpha(dart1);
            addDart(dart1);
            addDart(dart2);
            addEdgeToDarts(edge, new Dart[]{dart1, dart2});
            addVertexToEdge(edge);
        }
        for(Dart dart : this.darts){
            setSigma(dart);
//            System.out.println("Dart "+dart+" has sigma "+dart.getSigma()+" and alpha "+dart.getAlpha());
//            try{Thread.sleep(5000);}catch(Exception ex){}
            
        }
//        Dart[] dartsFrom34 = getDartsWhichStartAt(new Coordinate(200.0, 100.0));
//        for(Dart dart : dartsFrom34){
//            System.out.println("Dart "+dart+" has sigma "+dart.getSigma()+" and alpha "+dart.getAlpha());
//            char[] charArr = boundaryCheckFunctionString.toCharArray();
//            Dart bCheckDart = dart;
//                System.out.println("\t BoundaryCheck Start :: "+bCheckDart);
//            for(char c : charArr){
//                if(c=='a') {
//                    bCheckDart = bCheckDart.getAlpha();
//                }else if(c=='s'){
//                    bCheckDart = bCheckDart.getSigma();
//                }
//                System.out.println("\t BoundaryCheck Check "+c+" :: "+bCheckDart);
//            }
//
//            System.out.println(" - BoundaryCheck Goes to "+bCheckDart+
//                    " equals: "+dart.equals(bCheckDart));
//
//            Dart alphaBCheckDart = dart.getAlpha();
//                System.out.println("\t BoundaryCheck Start :: "+alphaBCheckDart);
//            for(char c : charArr){
//                if(c=='a') {
//                    alphaBCheckDart = alphaBCheckDart.getAlpha();
//                }else if(c=='s'){
//                    alphaBCheckDart = alphaBCheckDart.getSigma();
//                }
//                System.out.println("\t BoundaryCheck Check "+c+" :: "+alphaBCheckDart);
//            }
//
//            System.out.println(" - BoundaryCheck For Alpha Goes to "+alphaBCheckDart+
//                    " equals: "+dart.getAlpha().equals(alphaBCheckDart));
//            System.out.println(" - isBoundary "+(!
//                    (dart.equals(bCheckDart)&&dart.getAlpha().equals(alphaBCheckDart))
//                    ));
//        }
        //Order edge list by length
        sortEdgeListByLength(edges);

        //Get boundary edges
        setupBoundaryEdges();
        //Get boundary edges
        setupBoundaryVertices();
    }
    private void setSigma(Dart dart) throws CombinatorialMapDegenerateException{
        Dart[] dartsWhichStart = getDartsWhichStartAt(dart.getStart());
        double lowestAngle = 2*Math.PI;
        Dart currentNextDart = null;
        double anticlockwiseAngle;
        Edge dartEdge = dart.getEdge();
//        if(dart.getStart().equalsCheck(new Coordinate(1593.0, 474.0))){
//            System.out.println("Examining "+dart+" To set Sigma");
//        }
        for(Dart startDart : dartsWhichStart){
            if(startDart.equals(dart))continue;
            anticlockwiseAngle = dartEdge.getAngleAntiClockwiseFromMeTo(startDart.getEdge());
//            if(dart.getStart().equalsCheck(new Coordinate(1593.0, 474.0))){
//                System.out.println("\t Looking at angle from "+dart+" to "+startDart);
//                System.out.println("\t Angle is:" +anticlockwiseAngle+" :: "+Math.toDegrees(anticlockwiseAngle));
//            }
            if(anticlockwiseAngle<lowestAngle){
                currentNextDart = startDart;
                lowestAngle = anticlockwiseAngle;
            }
        }

        if(currentNextDart==null)
            throw new CombinatorialMapDegenerateException("Graph has degenerates, cannot build map, " +
                "no sigma for dart "+dart.toString());

//        if(dart.getStart().equalsCheck(new Coordinate(1593.0, 474.0))){
//            System.out.println("Set Sigma of "+dart+" To "+currentNextDart);
////            try{Thread.sleep(2000);}catch(InterruptedException ex){}
//        }
        dart.setSigma(currentNextDart);
    }

    private void addDart(Dart dart){
        if(!this.darts.contains(dart)){
            this.darts.add(dart);
            if(!this.vertexToDartEnd.containsKey(dart.getEnd())){
                this.vertexToDartEnd.put(dart.getEnd(), new ArrayList<Dart>());
            }
            this.vertexToDartEnd.get(dart.getEnd()).add(dart);
            if(!this.vertexToDartStart.containsKey(dart.getStart())){
                this.vertexToDartStart.put(dart.getStart(), new ArrayList<Dart>());
            }
            this.vertexToDartStart.get(dart.getStart()).add(dart);
        }
    }
    private void addEdgeToDarts(Edge edge, Dart[] darts){
        if(!this.edgeToDarts.containsKey(edge)&&darts.length==2){
//            System.out.println("Adding "+edge.getStart()+"->"+edge.getFinish()+" to edge to darts");
            this.edgeToDarts.put(edge, darts);
        }
    }
    private void addVertexToEdge(Edge edge){
        if(!this.vertexToEdges.containsKey(edge.getStart())){
            this.vertexToEdges.put(edge.getStart(), new ArrayList<Edge>());
        }
        if(!this.vertexToEdges.containsKey(edge.getFinish())){
            this.vertexToEdges.put(edge.getFinish(), new ArrayList<Edge>());
        }
        if(!this.vertexToEdges.get(edge.getStart()).contains(edge)){
            this.vertexToEdges.get(edge.getStart()).add(edge);
        }
        if(!this.vertexToEdges.get(edge.getFinish()).contains(edge)){
            this.vertexToEdges.get(edge.getFinish()).add(edge);
        }
    }
    private void sortEdgeListByLength(Edge[] edges){
        sortedEdges = new TreeSet<Edge>(getEdgeComparator());
        for(Edge edge : edges){
//            if(sortedEdges.contains(edge)){
//                System.out.println("Edge already contained"+edge.getStart()+"->"+edge.getFinish());
//                boolean foundEqual = false;
//                Iterator<Line> iter = sortedEdges.iterator();
//                while(!foundEqual && iter.hasNext()){
//                    Line test = iter.next();
//                    foundEqual = (test.getStart().equals(edge.getStart())&&test.getFinish().equals(edge.getFinish()));
//                }
//                System.out.println("Full Check "+(foundEqual?"agrees":"disagrees"));
//            }
            sortedEdges.add(edge);
        }
    }

    
    
    private void setupBoundaryEdges(){
        this.boundaryEdges = new TreeSet<Edge>(getEdgeComparator());
        for(Edge edge : this.sortedEdges){
            if(boundaryCheckFunction(edge)) {
                this.boundaryEdges.add(edge);
//                System.out.println("Boundary edge: "+edge.getStart()+"->"+edge.getFinish());

            }
        }
    }

    private void setupBoundaryVertices(){
        this.boundaryVertices = new ArrayList<Coordinate>();
        for(Edge edge: this.boundaryEdges){
            if(!this.boundaryVertices.contains(edge.getStart())){
                this.boundaryVertices.add(edge.getStart());
//                System.out.println("Boundary Vertex: "+edge.getStart());
            }
            if(!this.boundaryVertices.contains(edge.getFinish())){
                this.boundaryVertices.add(edge.getFinish());
//                System.out.println("Boundary Vertex: "+edge.getFinish());
            }
        }
    }


    public RevealFunctionResult revealFunction(Edge edge){
        Dart[] dartArr = getDartsOnEdge(edge);
        Dart[] result = new Dart[2];
        if(dartArr[0].function(boundaryCheckFunctionString).equals(dartArr[0])){
            result[0] = dartArr[0].function(revealIfDartIsOnBoundaryString);
        }else{
            result[0] = dartArr[0].function(revealIfDartIsNotOnBoundaryString);
        }
        if(dartArr[1].function(boundaryCheckFunctionString).equals(dartArr[1])){
            result[1] = dartArr[1].function(revealIfDartIsOnBoundaryString);
        }else{
            result[1] = dartArr[1].function(revealIfDartIsNotOnBoundaryString);
        }
        return new RevealFunctionResult(result[0].getEdge(),result[1].getEdge());
    }

    public boolean boundaryCheckFunction(Edge edge){
        Dart[] dartArr = getDartsOnEdge(edge);
        return !(dartArr[0].function(boundaryCheckFunctionString).equals(dartArr[0])&&
                dartArr[1].function(boundaryCheckFunctionString).equals(dartArr[1]));
    }



    /**
     * @return the edgeComparator
     */
    public EdgeComparator getEdgeComparator() {
        return edgeComparator;
    }

    public static class RevealFunctionResult{
        private Edge edge1,edge2;
        private Coordinate commonVertex;
        public RevealFunctionResult(Edge edge1, Edge edge2){
            this.edge1 = edge1;
            this.edge2 = edge2;
            //Assume there is a common vertex
            if(this.edge1.getStart().equals(edge2.getStart())||
                    this.edge1.getStart().equals(edge2.getFinish())){
                this.commonVertex = this.edge1.getStart();
            }else{
                this.commonVertex = this.edge1.getFinish();
            }
        }

        /**
         * @return the edge1
         */
        public Edge getEdge1() {
            return edge1;
        }

        /**
         * @return the edge2
         */
        public Edge getEdge2() {
            return edge2;
        }

        /**
         * @return the commonVertex
         */
        public Coordinate getCommonVertex() {
            return commonVertex;
        }
    }


    public class EdgeComparator implements Comparator<Edge>{

        public int compare(Edge arg0, Edge arg1) {
            double lengthSQ1 = arg0.getStart().getDistanceSquared(arg0.getFinish());
            double lengthSQ2 = arg1.getStart().getDistanceSquared(arg1.getFinish());
            if(lengthSQ1==lengthSQ2){
                int startDiff = arg0.getStart().compareByMinXMinY(arg1.getStart());
                if(startDiff!=0) return startDiff;
                return arg0.getFinish().compareByMinXMinY(arg1.getFinish());
            }
            if(lengthSQ1>lengthSQ2) return -1;
            return 1;
        }
        
    }
}
